Hand-held computers and personal assistants such as the 3Com PalmPilot (PaImPilot is a trademark of 3Com Corporation) are rapidly improving in performance, allowing to execute such applications as word processing, diaries, database access and management. An example of database management software is the program List version 0.93 by Andrew Low, which can be installed and operated on a 3Com PaImPilot computer.
Portable GPS receivers are being used for a variety of applications that query a database using the current location of the GPS receiver, to obtain various information dependent upon the location of the GPS receiver and time. An example of use of a GPS receiver for obtaining information dependent upon the location of the device is the Hertz NeverLost system (NeverLost is a trademark of the Hertz Corporation), used in combination with a motor vehicle to instruct the driver of the proper directions to reach a specific destination.
In the prior art, GPS receivers are used to collect data to form a database. An example of use of a GPS receiver to collect data to form or complete a database is provided in U.S. Pat. No. 5,699,244 entitled HAND-HELD GUI PDA WITH GPS/DGPS RECEIVER FOR COLLECTING AGRONOMIC AND GPS POSITION DATA by Clark et al., that is herein incorporated by reference in its entirety. Clark et al. 's device comprises a probe used to collect coordinates of objects of interest in the vicinity of the device.
One example of database is a geographic database or Geographic Information System (GIS). One system for collecting data to form a geographic database is described in U.S. Pat. No. 5,528,518 entitled SYSTEM AND METHOD FOR COLLECTING DATA USED TO FORM A GEOGRAPHIC INFORMATION SYSTEM DATABASE by Bradshaw et al., which is herein incorporated by reference in its entirety. Using the system described by Bradshaw et al., a variety of devices can be used to collect the data.
Location data as provided by a GPS receiver is also used to query a geometry database and collect geometric data used to display three-dimensional renderings of the surroundings of the spatial location specified in the location data. A three-dimensional geometry database typically comprises vertices which are connected by polygons or triangles and edges. For a more detailed description, see U.S. patent application Ser. No. 006,771 entitled COMPRESSED REPRESENTATION OF CHANGING MESHES AND METHOD TO DECOMPRESS, filed Jan. 14, 1998 by G. Taubin and A. Gueziec, U.S. patent application Ser. No. 023,757, entitled PROGRESSIVE MULTI-LEVEL TRANSMISSION AND DISPLAY OF TRIANGULAR MESHES by A. Gueziec, G. Taubin and F. Lazarus, and U.S. patent application Ser. No. 976,247 entitled PROGRESSIVE COMPRESSION OF CLUSTERED MULTI-RESOLUTION POLYGONAL MODELS all of which are herein incorporated by reference in their entirety, as well as U.S. Patent Application XXX, entitled SYSTEM AND METHOD FOR FINDING THE DISTANCE FROM A MOVING QUERY POINT TO THE CLOSEST POINT ON ONE OR MORE CONVEX OR NON-CONVEX SHAPES, and previously incorporated by reference.
A query point is a point for which it is sought to compute the distance and one or more closest features on the geometry database. A closest feature is either a point, edge or polygon. A query point generally has one closest polygon, one closest edge and one closest vertex on the geometry database. An example of a system providing access to a three-dimensional geometry database and displaying three-dimensional renderings is described in U.S. Pat. No. 5,381,338 entitled REAL TIME THREE DIMENSIONAL GEO-REFERENCED DIGITAL ORTHOPHOTOGRAPH-BASED POSITIONING, NAVIGATION, COLLISION AVOIDANCE AND DECISION SUPPORT SYSTEM by Wysocki et al., which is herein incorporated by reference in its entirety.
In U.S. Pat. No. 5,781,150 entitled GPS RELATIVE POSITION DETECTION SYSTEM, by Norris et al., which is herein incorporated by reference in its entirety, a device is used for displaying the geographical location of the device with respect to another object and providing an approximate direction of travel and distance to the object from the device.
In U.S. Pat. No. 5,289,195 entitled POSITIONING AND DISPLAYING SYSTEM by Inoue et al., which is herein incorporated by reference in its entirety, an apparatus is described for locating a current position on a map.
Chiang et al., in the publication entitled "Dynamic Algorithms in Computational Geometry" in Proceedings of the IEEE, Vol 80. No. 9, September 1992, pages 1412-1434, which is herein incorporated by reference in its entirety, describe a method for locating a point in a planar triangulation using data structures representing two-dimensional trees.